// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore()
{
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
Semaphore::P()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to Sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V()
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

// Dummy functions -- so we can compile our later assignments 
// Note -- without a correct implementation of Condition::Wait(), 
// the test case in the network assignment won't work!
Lock::Lock(char* debugName) {		//initialize lock status, lock owner, wait queue.
	name = debugName;
	lockStatus = 1;			//make lock free.
	lockOwner = NULL;		//no Thread owns the lock
	queue = new List;
}

Lock::~Lock() {
	delete queue;
}

void Lock::Acquire() {
	IntStatus oldLevel = interrupt->SetLevel(IntOff); //disable interrupt
	//If I am the owner
	if(lockOwner==currentThread){		
		//printf("I own the lock~~\n");
		interrupt->SetLevel(oldLevel);		//restore interrupt
		return;
	}
	
	if (lockStatus==1){		//lock is available
		lockStatus = 0;		//make lock busy
		lockOwner = currentThread;	//i'm the lock owner
	}
	else{	//lock is not available
		queue->Append((void *)currentThread);//add myself to wait queue.
		currentThread->Sleep();		//wait for the lock available
		lockOwner = currentThread;		//i'm the lock owner
	}
	
	interrupt->SetLevel(oldLevel); //restore interrupt			
}

void Lock::Release() {
	Thread *thread;
	bool ownership;								
	IntStatus oldLevel = interrupt->SetLevel(IntOff); //disable interrupts
	ownership = isHeldByCurrentThread(); //judgement the ownership. if currentThread owns the lock, return TRUE, or return FALSE.
	if(ownership==FALSE){	//currentThread does not own this lock.	
		printf("Stop! You are trying to release the wrong key\n");
		interrupt->SetLevel(oldLevel);	//restore the interrupt	
		return;
	}
	thread = (Thread *)queue->Remove();	//remove the head thread of the waiting queue 	
	if(thread!=NULL){		//waiting queue is not empty
		scheduler->ReadyToRun(thread);	//ready to run
		lockOwner = NULL;
	}
	else{
		lockStatus = 1;		//set lock status - free
		lockOwner = NULL;	//no Thread owns the lock
	}
	interrupt->SetLevel(oldLevel);	//restore the interrupt
}
//tell whether currentThread owns this lock
bool Lock::isHeldByCurrentThread(){	
	if(lockOwner==currentThread)	//owner of this lock
		return TRUE;
	else					//not the owner of this lock
		return FALSE;
}
//initialize waitinglock and waitqueue.		
Condition::Condition(char* debugName) {	
	name = debugName;
	waitingLock = NULL;
	waitQueue = new List;
}
Condition::~Condition() { 
	delete waitQueue;
}
void Condition::Wait(Lock* conditionLock) { 			
	bool ownership;
	IntStatus oldLevel = interrupt->SetLevel(IntOff); //disable interrupts
	ownership = conditionLock->isHeldByCurrentThread();	//tell whether currentThread owns this lock
	if(ownership!=TRUE){		//currentThread does not own this lock
		printf("wait:not own the lock, acquire it\n");
		interrupt->SetLevel(oldLevel);			//restore the interrupt
		return;
	}
	if(conditionLock==NULL){		//there is no lock  
		printf("wait:no lock, plz acquire the lock first\n");
		interrupt->SetLevel(oldLevel);		//restore the interrupt
		return;
	}
	if(waitingLock==NULL){   //fist waiting thread
		waitingLock=conditionLock; //set waiting lock
	}
	//judgement whether currentThread is in the wait condition for the right lock
	if(waitingLock!=conditionLock){		//locks are different
		printf("you are waiting for the wrong lock\n");
		interrupt->SetLevel(oldLevel);	//restore interrupt
		return;
	}
	conditionLock->Release();			//release lock
	waitQueue->Append((void*)currentThread);	//add currentThread to the waitQueue of wait conditions.
	currentThread->Sleep();			//sleepZZZZZ
	conditionLock->Acquire();		//acquire for the lock
	
	interrupt->SetLevel(oldLevel);	//restore interrupt
	//ASSERT(FALSE);	
}

void Condition::Signal(Lock* conditionLock) {
	Thread* thread;
	bool ownership;
	bool wait;
	IntStatus oldLevel = interrupt->SetLevel(IntOff);		//disable interrupt
	ownership = conditionLock->isHeldByCurrentThread();		//judge the ownership of the lock
	if(ownership!=TRUE){		//currentThread doesn't own this lock
		printf("Single:not own the lock, acquire it\n");
		interrupt->SetLevel(oldLevel); //restore interrupt
		return;
	}
	thread = (Thread *)waitQueue->Remove(); //remove one thread from the waitqueue
	if(thread == NULL){		//waitqueue is empty
		printf("no thread waiting\n");
		interrupt->SetLevel(oldLevel);	//restore interrupt
		return;
	}
	if(waitingLock!=conditionLock){	//locks are different
		printf("wrong lock\n");
		interrupt->SetLevel(oldLevel);	//restore interrupt
		return;
	}
	//wake up waiting thread
	scheduler->ReadyToRun(thread);	//ready to run
	wait = waitQueue->IsEmpty();	//judge waitqueue whether is empty or not
	if(wait==TRUE)		//waitqueue is empty
		waitingLock=NULL;
		
	interrupt->SetLevel(oldLevel);	//restore interrupt
	return;
}

void Condition::Broadcast(Lock* conditionLock) {
	while((waitQueue->IsEmpty())!=TRUE){	//waitqueue is not empty
		Signal(conditionLock);
	}
}

